Discrete Probability

An introduction

Finite Probability

An experiment is a procedure that gives a set of outcomes. This set of all possible outcomes is called the Sample Space, SS
We will for now, assume that 0<S<+0 \lt |S|\lt+\infty

We also make the basic assumption that each outcome in the sample space, SS, is equally likely to happen

An event, EE, is a subset of SS - That is ESE\subseteq S

Definition The probability of an event ESE \subseteq S, where SS is a finite sample space with equally likely outcomes is

P(E)=ES P(E)=\frac{|E|}{|S|}

A typical simple sample space SS would be the roll of a fair die, or the toss of a pair of dice, the cut of a deck of playing cards, the choice of 6 numbers ont of 49 etc

Example 1

Consider a 6 sided fair die

The outcomes possible are

S1={1,2,3,4,5,6} \mathcal{S}_{1}=\{1,2,3,4,5,6\}

Let EE be the event that the outcome is an even integer
Then E={3,4,6}E=\{3,4,6\} and P(E)=36=12\displaystyle P(E)=\frac{3}{6}=\frac{1}{2}.

Example 2

Consider the toss of two fair distinguishable dice
Then the sample space is, using the same notation as Exercise 1,

S2=S1×S1={(x,y)x,yS,}={(1,1),(1,2),(1,3),,(6,5),(6,6)} \begin{aligned} S_{2} & =S_{1} \times S_{1}=\{(x, y) \mid x, y \in S,\} \\ & =\{(1,1),(1,2),(1,3), \cdots,(6,5),(6,6)\} \end{aligned}

Clearly S2=66=36\left|S_{2}\right|=6\cdot 6=36.


Let E1E_{1} be the event that the two dice add up to 7 .

Then E1={(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)}thus E1=6E_{1}=\{(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)\}\quad thus\ \mid E_1 \mid =6

P(E1)=636=16\therefore \quad P\left(E_{1}\right)=\frac{6}{36}=\frac{1}{6}

Let E2E_{2} be the event that the two dice come up the same
Clearly E2=6\left|E_{2}\right|=6 and hence P(E2)=16P\left(E_{2}\right)=\frac{1}{6}


Let E3E_{3} be the outcome die#1 > die#2

 Then E3= {(2,1),(3,1),(3,2),(4,1),(4,2),(4,3),(5,1),(5,2),(5,3),(5,4),(6,1),(6,2),(6,3),(6,4),(6,5)},E3 =15 \begin{aligned} \text { Then } E_{3}=\ \{\quad&(2,1),(3,1),(3,2),\\ &(4,1),(4,2),(4,3),\\ &(5,1),(5,2),(5,3),\\ &(5,4),(6,1),(6,2),\\ &(6,3),(6,4),(6,5)\quad\},\\ \mid E_{3} \mid\ =15 \end{aligned}

and P(E3)=1536=512P\left(E_{3}\right)=\frac{15}{36}=\frac{5}{12}.

Example 3

Consider Lotto 649
What is the probability that the 6 numbers you pick will win the grand prize?

Here the sample space SS is all possible ways to pick 6 out of 49 .

Thus S=(496)|S|=\left(\begin{array}{c}49 \\ 6\end{array}\right)

Here our event EE is the outcome where the exact 6 numbers you picked are the ones that fall out of the drum. Thus E=1|E|=1 and

P(E)=1S=(496)1=6543214948474634544=1494746344=113,983,816 \begin{aligned} P(E) & =\frac{1}{|S|}=\left(\frac{49}{6}\right)^{-1}=\frac{\cancel{6}\cdot\cancel{5} \cdot\cancel{4} \cdot\cancel{3}\cdot\cancel{2}\cdot1}{49\cdot\cancel{48} \cdot47 \cdot 46\cdot _3^{\cancel{45}} \cdot44} \\ & =\frac{1}{49\cdot47\cdot46\cdot3\cdot44}=\frac{1}{13,983,816} \end{aligned}

Example 4

What in the probability that the 5 card hand you get dealt from a standard playing deck is all one suit?

Here S=S= all 5 card hands and

S=(525) \mid S\mid =\left(\begin{array}{c} 52 \\ 5 \end{array}\right)  Spades =13 Hearts =13 Diamonds =13 Clubs =13 \begin{aligned} & \textbf { Spades }&=13 \\ & \textbf { Hearts }&=13 \\ & \textbf { Diamonds }&=13 \\ & \textbf { Clubs }&=13 \end{aligned}

E=E= all cards from one suit and E=4(135) \begin{aligned} & |E|=4 \cdot\left(\begin{array}{c} 13 \\ 5 \end{array}\right) \end{aligned} and

P(E)=4(135)(525)=411311211110193452175155049150=113417549=3368600.0048(=0.48%) P(E) = \frac{4\cdot \left(\begin{array}{c} 13 \\ 5 \end{array}\right)}{\left(\begin{array}{c} 52 \\ 5 \end{array}\right)} = \frac{ _{\cancel{4}}^1\cdot _{\cancel{13}}^1\cdot _{\cancel{12}}^1\cdot 11 \cdot _{\cancel{10}}^1\cdot _{\cancel{9}}^3\cdot }{_4^{\cancel{52}} \cdot _{17}^{\cancel{51}} \cdot _5^{\cancel{50}} \cdot 49 \cdot _1^{\cancel{50}}} = \frac{11\cdot 3}{4 \cdot 17 \cdot 5 \cdot 49} =\frac{33}{6860}\\ \doteqdot 0.0048(=0.48 \%)

Note It is always true that 0P(E)1 0 \leq P(E) \leq 1

Further Facts

  1. Let ESE \subseteq S The event that EE does not occur
    Eˉ\bar{E} is the complement of EE in SS
Eˉ=SE |\bar{E}|=|S|-|E|

so P(Eˉ)=SES=1ES=1P(E)\displaystyle P(\bar{E})=\frac{|S|-|E|}{|S|}=1-\frac{|E|}{|S|}=1-P(E)

  1. Let E1+E2E_{1}+E_{2} be two events in SS,

Then P(E1E2)=P(E1)+P(E2)P(E1E2) P\left(E_{1} \cup E_{2}\right)=P\left(E_{1}\right)+P\left(E_{2}\right)-P\left(E_{1} \cap E_{2}\right)

by the rule of inclusion-exclusion

Examples

  1. The Birthday Problem.

A group of nn people has gathered. We want to find the probability that we can find a pair of people with the same birthday

We must make the assumption that all birthdays are equally likely (not true).

We also assume that Feb 29 = Feb 28\text{Feb 29 = Feb 28} , so that there are 365 possible birthdays

We let E=E= at least one pair of people have the same birthday

We will find P(Eˉ)P(\bar{E}) and then P(E)=1P(Eˉ)P(E)=1-P(\bar{E})

Now Eˉ=|\bar{E}|= number ways nn people have different birthdays

=365364363(365n+1)(=P(365,n)) =365 \cdot 364 \cdot 363 \cdots(365-n+1)(=P(365, n))

The total number of ways that nn people can

Have birthdays is 365n=S365^{n}=|S|

Thus P(Eˉ)=365364(365n+1)365n=364363(366n)365n1P(\bar{E})=\frac{365 \cdot 364 \cdots(365-n+1)}{365^{n}} =\frac{364 \cdot 363 \cdot \ldots \cdot(366-n)}{365^{n-1}}

and P(E)=1P(364,n1)365n1P(E)=1-\frac{P(364, n-1)}{365^{n-1}}

Exercise What is the minimum number, nn, such that P(E)12P(E) \geqslant \frac{1}{2} ?
Hint : this implies P(Eˉ)<12P(\bar{E})<\frac{1}{2}
This is best done by trial and error?

  1. Let's Make a Deal

You are given the choice of picking one of 3 doors to win the grand prize

You pick a door. The host then opens one of the other 2 doors and shows you that it was a "losing door", You are then offered the choice of switching doors

What should you do?

Since the doors are equally likely that they hide the jackpot, the probability that your choice was correct is 13\frac{1}{3}, and wong is 23\frac{2}{3}.

Thu the probability that the other two dooms hid the jackpot is 23\frac{2}{3}, and since this is not affected by the opening of a losing dore, the probability that your door is wrong is still 23\frac{2}{3} ?

Thus the other door is the night choice with a probability of 23\frac{2}{3}, so switch doors


  1. What in the probability that a card selected from a deck is an ace?

Solution
Let S={S=\{ deck of cards, S=52|S|=52

Let E={E=\{ an ace is picked },E=4\},|E|=4

P(E)=ES=452=113 \therefore\quad P(E)=\frac{|E|}{|S|}=\frac{4}{52}=\frac{1}{13}

Example 4

What is the probability that a 5 card poker hand contains the ace of hearts

Solution Let S={5S=\{5 card poker hands }\}

S=(525) |S|=\left(\begin{array}{c} 52 \\ 5 \end{array}\right)

Let E={5E=\{5 card hand with A}A \hearts\}

E=(514) why? P(E)=(514)/(525)=51 50 49 484 3 2 15 4 3 2 152 51 50 49 48=552 \begin{aligned} &|E|=\left(\begin{array}{c} 51 \\ 4 \end{array}\right) \quad\text { why? } \\ & \therefore P(E)=\left(\begin{array}{c} 51 \\ 4 \end{array}\right) \Bigg/\left(\begin{array}{c} 52 \\ 5 \end{array}\right) \\ &=\frac{\cancel{51}\ \cancel{50}\ \cancel{49}\ \cancel{48}}{\cancel{4}\ 3\ 2\ 1}\cdot\frac{5\ \cancel{4}\ \cancel{3}\ \cancel{2}\ \cancel{1}}{52\ \cancel{51}\ \cancel{50}\ \cancel{49}\ \cancel{48}}=\frac{5}{52} \end{aligned}

Example 5

What is the probability that a 5 card poker hand has two pairs?

Solution Let E={5E=\{5 card hands with two pairs }\}

 Then E=pick the value of the pairs(132)(42)(42)(441)pick the fifth cardpick the two cards with one of the given values \text { Then }|E|=\\[1em] \text{pick the value of the pairs}\rightarrow\left(\begin{array}{c} 13 \\ 2 \end{array}\right) \cdot\left(\begin{array}{c} 4 \\ 2 \end{array}\right) \cdot\left(\begin{array}{c} 4 \\ 2 \end{array}\right) \cdot\left(\begin{array}{c} 44 \\ 1 \end{array}\right) \rightarrow \text{pick the fifth card}\\ \quad\quad\uparrow\\ \text{pick the two cards with one of the given values} =1312214321432144=136344 \begin{aligned} & =\frac{13 \cdot 12}{2 \cdot 1} \cdot \frac{4\cdot3}{2 \cdot 1} \cdot \frac{4\cdot3}{2\cdot1} \cdot 44 \\ & =13 \cdot 6^{3} \cdot 44 \end{aligned}

Thus

P(E)=136344(525)=123,5522,598,960=1984,1650.0475=4.75% \begin{aligned} P(E) & =\frac{13\cdot6^{3} \cdot 44}{\left(\begin{array}{c} 52 \\ 5 \end{array}\right)} \\ & =\frac{123,552}{2,598,960}=\frac{198}{4,165} \\ & \doteqdot 0.0475=4.75\% \end{aligned}

Exercises §7.1 p 475 # 1 - 18, 24, 25\text{\S 7.1 p 475 \# 1 - 18, 24, 25}

Discrete Probability

So far we have dealt only with the very restricted case where our sample space SS is finite and each outcome in (ie., element of) SS and is equally likely

This is insufficient on two counts

  1. We often deal with experiment where the sample space is not finite. when SS is infinite it can be countable or uncountable

When SS is countable S 0|S| \leq\ \alef_0 we talk about Discrete sample spaces and when SS is uncountable we talk about Continuous sample spaces The analysis of Continuous Probability requires calculus methods (see M2236)

  1. All outcomes need not he equally, likely
    For example an "unfair" die 1 may come up more often than 6 does

To deal with these situations we will develop a theory of Probability for Discrete Sample Spaces

Let SS be a countable sample space (finite or infinite) and sSs \in S be an outcome. We assign a probability p(s)p(s) to each outcome. so that P:SRP: S \rightarrow \mathbb{R} satisfies the following

i) 0p(s)10 \leqslant p(s) \leq 1

ii) sSp(s)=1\displaystyle\sum_{s\in S} p(s)=1

Note i) {no negative probabilities,  no probabilities >1\Rightarrow\Bigg\{\begin{array}{l}n o \text { negative probabilities, } \\ \text { no probabilities }>1 \end{array}

ii) If S=n<+|S|=n<+\infty, then with S={s1,,sn}S=\left\{s_{1}, \cdots, s_{n}\right\},

k=1np(sk)=1 \sum_{k=1}^{n} p\left(s_{k}\right)=1

If S=0|S|=\alef_{0}, then with S={s1,s2,}S=\left\{s_{1}, s_{2}, \ldots\right\}

k=1p(sk)=1convergent infinite series \sum_{k=1}^{\infty} p\left(s_{k}\right)=1\qquad \text{convergent infinite series}

This imposes "severe" restrictions on pp

If p:SRp: S \rightarrow \mathbb{R} satisfies i) and ii) we call p(s)p(s) a probability distribution on SS

Now let ESE \subseteq S be an event, we define

P(E)=sEP(s). P(E)=\sum_{s \in E} P(s) .

That is the probability of an event is the sum of the probabilities of all the outcomes that comprise the event

This definition of probability also exhibits the properties of Finite probability mentioned earlier

  1. P(Eˉ)=1P(E)P(\bar{E})=1-P(E)

  2. P(E1E2)=P(E1)+P(E2)P(E1E2)P\left(E_{1} \cup E_{2}\right)=P\left(E_{1}\right)+P\left(E_{2}\right)-P\left(E_{1} \cap E_{2}\right)

and one further property

  1. P(iEi)=iP(Ei)P\left(\cup_{i} E_{i}\right)=\sum_{i} P\left(E_{i}\right)

for all pairwise disjoint events E4,E2,E_{4}, E_{2}, \ldots

Examples

  1. Let us have a die. that comes up 1 or 6 twice as often as all other numbers

Here S={1,2,3,4,5,6}S=\{1,2,3,4,5,6\}

and

p(1)=p(6)=2p(2)=2p(3)=2p(4)=2p(5) p(1)=p(6)=2 p(2)=2 p(3)=2 p(4)=2 p(5)

and

1=k=16p(k)=p(1)+p(2)+p(3)+p(4)+p(5)+p(6)=2p(2)+p(2)+p(2)+p(2)+p(2)+2p(2)=8p(2) \begin{aligned} 1 & =\sum_{k=1}^{6} p(k)=p(1)+p(2)+p(3)+p(4)+p(5)+p(6) \\ & =2 p(2)+p(2)+p(2)+p(2)+p(2)+2 p(2) \\ & =8 p(2) \end{aligned}

p(2)=18=p(3)=p(4)=p(5)\therefore \quad p(2)=\frac{1}{8}=p(3)=p(4)=p(5)

For this probability distribution, ie for this die, what is the probability that 2 rolls of this die add up to less than 6

S={(1,1),(1,2),,(6,5),(6,6)}E={(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(3,1),(3,2),(4,1)}P(1,1)=1414=116P(1,2)=1418=132P(1,3)=132=P(1,4)P(2,1)=132,P(2,2)=164P(2,3)=164P(3,1)=132P(3,2)=164P(4,1)=132P(E)=sEP(s)=116+632+364+464+1264+364=1964 \begin{aligned} & S=\{(1,1),(1,2),\cdots ,(6,5),(6,6)\} \\ & E=\{(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(3,1),(3,2),(4,1)\} \\ & P(1,1)=\frac{1}{4} \cdot \frac{1}{4}=\frac{1}{16}\qquad P(1,2)=\frac{1}{4} \cdot \frac{1}{8}=\frac{1}{32} \\ & P(1,3)=\frac{1}{32}=P(1,4)\qquad P(2,1)=\frac{1}{32},\qquad P(2,2)=\frac{1}{64} \\ & P(2,3)=\frac{1}{64}\qquad P(3,1)=\frac{1}{32}\qquad P(3,2)=\frac{1}{64}\qquad P(4,1)=\frac{1}{32} \\ & P(E)=\sum_{s \in E} P(s)=\frac{1}{16}+\frac{6}{32}+\frac{3}{64}+\frac{4}{64}+\frac{12}{64}+\frac{3}{64}=\boxed{\frac{19}{64}} \end{aligned}
  1. Consider the following experiment A fair coin is tossed repeatedly until a Heads occurs
    (P(H)=P(T)=12)(P(H)=P(T) =\frac{1}{2})

The sample space consists of the number of tosses until we get an HH

Clearly S={1,3,4,}S=\{1,3,4, \cdots\}

This type of situation is called Repeated Bernoulli Trials
a Bernoulli Trial is an experiment with only 2 possible outcomes called success or failure
If p(p( success )=θ)=\theta, then p(p( fail )=1θ)=1-\theta

Repeated Bernoulli Trails are when, we examine the outcome of independent trials the result on this flip of the coin doesn't depend on previous flips outcomes In this case the probability of a repeated trial is the product of the probability of each individual trial

For repeated flips of a fair coin
The probability that the first HH occurs on the n th n \frac{\text { th }}{} toss is 12n\displaystyle\frac{1}{2^{n}} since this is the outcome

T T TTn1 tails H first head12121212=12n \begin{aligned} \\ &\underbrace{T\ T\ T \cdots T}_{n-1 \text { tails }} \cdot H \leftarrow\text{ first head}\\ &\overbrace{\frac{1}{2}\cdot\frac{1}{2}\cdots\frac{1}{2}} \cdot \frac{1}{2}=\frac{1}{2^{n}} \end{aligned}

Define therefore the probability function

p(n)=12n,n=1,2,3, p(n)=\frac{1}{2^{n}},\qquad n=1,2,3, \cdots

Clearly 0p(n)1,n=1,20 \leq p(n) \leq 1,\quad \forall n=1,2 \cdots\qquadso property i) is satisfied

as for property ii)

sSp(s)=n=1+12n=n=1+(12)n=12(1112)=12+14+18+=1 \begin{aligned} \sum_{s \in S} p(s) & =\sum_{n=1}^{+\infty} \frac{1}{2^{n}}=\sum_{n=1}^{+\infty}\left(\frac{1}{2}\right)^{n}=\frac{1}{2}\left(\frac{1}{1-\frac{1}{2}}\right) \\[2em] & =\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots=1 \end{aligned}

Exercise: What is the probability that the first H occurs on,
an even numbered toss? , an odd numbered toss?

E1={E_{1}=\{ first HH is on an even numbered toss }\}

E2={E_{2}=\{ first HH is on an odd numbered toss }\}

Clearly E1=Eˉ2E_{1}=\bar{E}_{2} so p(E1)=1p(E2)p\left(E_{1}\right)=1-p\left(E_{2}\right)

 Now P(E1)=n=1P(2n)=n=1122n=n=1(14)n=14+142+143=14[1+14+142+143+]=141114=141(34)=13P(E1)=13,P(E2)=23 \begin{aligned} \text { Now }\qquad P\left(E_{1}\right) & =\sum_{n=1}^{\infty} P(2 n)=\sum_{n=1}^{\infty} \frac{1}{2^{2 n}} \\[2em] & =\sum_{n=1}^{\infty}\left(\frac{1}{4}\right)^{n}=\frac{1}{4}+\frac{1}{4^{2}}+\frac{1}{4^{3}} \\[2em] & =\frac{1}{4}\left[1+\frac{1}{4}+\frac{1}{4^{2}}+\frac{1}{4^{3}}+\cdots\right] \\[2em] & =\frac{1}{4} \cdot \frac{1}{1-\frac{1}{4}}=\frac{1}{4} \cdot \frac{1}{\left(\frac{3}{4}\right)}=\frac{1}{3} \\[2em] P\left(E_{1}\right) =\frac{1}{3},\qquad P\left(E_{2}\right)=\frac{2}{3} \end{aligned}

(17)

\#2 on Exercise sheet for L19&20L 19 \& 20

What is the probability that a bit string of length 10 will

a) Start with 2 zeroes or end with 3 ones?

Here S={S=\{ bit strings of length 10}=Bit10\}=B_{i} t_{10}

S=210E={ start with 00, er end with 111}E=E1E2E1={ start with 00}E2={ end with 111}E1=28E2=27E1E2=25E=28+2725=352P(E)=352210=1132 \begin{aligned} & |S|=2^{10} \\ & E=\{\text { start with } 00 \text {, er end with } 111\} \\ & E=E_{1} \cup E_{2} \quad E_{1}=\{\text { start with } 00\} \\ & E_{2}=\{\text { end with } 111\} \\ & \left|E_{1}\right|=2^{8}\left|E_{2}\right|=2^{7}\left|E_{1} \cap E_{2}\right|=2^{5} \\ & |E|=2^{8}+2^{7}-2^{5}=352 \\ & P(E)=\frac{352}{2^{10}}=\frac{11}{32} \end{aligned}

(18)

b) Contain exactly 3 ones

E={ exactly 3 ones }E=(103)=10984x21P(E)=120210=15128=120 \begin{array}{ll} E=\{\text { exactly } 3 \text { ones }\} \quad|E|=\left(\begin{array}{l} 10 \\ 3 \end{array}\right)=\frac{10 \cdot 9 \cdot 8^{4}}{x \cdot 2 \cdot 1} \\ P(E)=\frac{120}{2^{10}}=\frac{15}{128} & =120 \end{array}

c) Ec={E_{c}=\{ less them 4 ones }\}

Ec=(100)+(101)+(102)+(103)=1+10+45+120=176P(E=176210=1164 \begin{aligned} \left|E_{c}\right| & =\left(\begin{array}{c} 10 \\ 0 \end{array}\right)+\left(\begin{array}{c} 10 \\ 1 \end{array}\right)+\left(\begin{array}{c} 10 \\ 2 \end{array}\right)+\left(\begin{array}{c} 10 \\ 3 \end{array}\right) \\ & =1+10+45+120=176 \\ P(E & =\frac{176}{2^{10}}=\frac{11}{64} \end{aligned}

d)

Ed={ contaexis at least 4 ones }=EˉcP(Ed)=1P(Ec)=11164=5364 \begin{aligned} & E_{d}=\{\text { contaexis at least } 4 \text { ones }\}=\bar{E}_{c} \\ & P\left(E_{d}\right)=1-P\left(E_{c}\right)=1-\frac{11}{64}=\frac{53}{64} \end{aligned}